package tree;

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int temp=0;
        int[] arr = new int[]{7,4,9,8,3,2,1,6};
        //进行有序化排序第一个值为最大值
        for (int i=arr.length/2-1 ; i >=0 ; i--) {
            adjustSort(arr,i,arr.length);
        }
        for(int i =arr.length-1;i>0;i--){
            temp=arr[i];
            arr[i]=arr[0];
            arr[0]=temp;
            adjustSort(arr,0,i);
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     * @param arr    要排序的数组
     * @param i      非叶子节点数组索引
     * @param length 长度
     */
    public static void adjustSort(int[] arr, int i, int length) {
        int temp = arr[i];
        for(int x=i*2+1;x<length;x=x*2+1){
            if(x+1<length&&arr[x]<arr[x+1]){
                x++;
            }
            if(arr[x]>arr[i]){
                arr[i]=arr[x];
                i=x;
            }
        }
        arr[i]=temp;
    }
}

